package fxy.fxyOffer;


/**
 * �����������
 * ��̬�滮
 * 1,2,5,3,4;
 * һ������d�������ÿһ��Ԫ�ض�Ӧ��������С�
 * ����d[0] = 1;A[0] = 1;
 * d[1] = 2;A[1] = {1,2};
 * ��1����ôd[2]����������£� 5>1  �𣿴�����ô���Լ���a[0] {1,5}��ߡ�
 * ��2��5>2�𣬴��ڣ���ô���Լ���A[1]��ߣ�ͬʱ����d[2] > ��һ�θ��µ�d[2] ;{1,2,5}
 * 
 */
public class LongestAscendingSubsequence {
	public void longestAscend(int a[]){
		int length = a.length;
		int []d = new int[length];
		int max = -1;
		for(int i = 0 ; i < length; i++){
			d[i] = 1;
		}
		for(int i = 1; i < length; i++){
			for(int j = 0 ; j < i ; j++){
				if (a[i] > a[j] && d[i] < d[j] + 1) {
					d[i] = d[j] + 1;
				}
			}
			if(d[i] > max){
				max = d[i];
			}
		}
		System.out.println(max);
	}
	public static void main(String[] args) {
		int a[] = {5,4,3,2,2,2};
		new LongestAscendingSubsequence().longestAscend(a);;
	}
}
